Operator Norm Inequalities between Tensor Unfoldings on the Partition Lattice

摘要

Interest in higher-order tensors has recently surged in data-intensivefields, with a wide range of applications including image processing, blindsource separation, community detection, and feature extraction. A commonparadigm in tensor-related algorithms advocates unfolding (or flattening) thetensor into a matrix and applying classical methods developed for matrices.Despite the popularity of such techniques, how the functional properties of atensor changes upon unfolding is currently not well understood. In contrast tothe body of existing work which has focused almost exclusively onmatricizations, we here consider all possible unfoldings of an order-$k$tensor, which are in one-to-one correspondence with the set of partitions of$\{1,\ldots,k\}$. We derive general inequalities between the $l^p$-norms ofarbitrary unfoldings defined on the partition lattice. In particular, wedemonstrate how the spectral norm ($p=2$) of a tensor is bounded by that of itsunfoldings, and obtain an improved upper bound on the ratio of the Frobeniusnorm to the spectral norm of an arbitrary tensor. For specially-structuredtensors satisfying a generalized definition of orthogonal decomposability, weprove that the spectral norm remains invariant under specific subsets ofunfolding operations.